from collections import deque
from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = deque()
        ans = []
        for i in range(len(nums)):
            while que and que[0] <= (i - k):
                que.popleft()
            while que and nums[i] > nums[que[-1]]:
                que.pop()
            que.append(i)
            if i >= k - 1:
                ans.append(nums[que[0]])
        return ans


if __name__ == '__main__':
    s = Solution()
    r = s.maxSlidingWindow(nums=[1, 3, 1, 2, 0, 5], k=3)
    print(r)
